package test230531;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/31 15:57
 * 213. 打家劫舍II
 * https://leetcode.cn/problems/house-robber-ii/
 */
public class Solution03 {

    public int rob(int[] nums) {
        // 分类讨论:
        // 0 位置偷 -> 1 和 n-1 位置不能偷 -> 2 - n-2 范围的打家劫舍I问题
        // 0 位置不偷 -> 1 - n-1 范围的打家劫舍I问题
        int n = nums.length;
        return Math.max(nums[0] + myRob(nums, 2, n-2), myRob(nums, 1, n-1));
    }

    // 处理打家劫舍I问题
    public int myRob(int[] nums, int left, int right) {
        if (left > right) {
            return 0;  // 处理边界
        }
        // f[i] g[i] 分别表示 i 位置偷与不偷的最大价值
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left] = nums[left];
        for (int i = left + 1; i <= right; ++i) {
            f[i] = g[i-1] + nums[i];  // 当前位置偷则为上一家不偷的最大价值加上该位置的价值
            g[i] = Math.max(g[i-1], f[i-1]); // 当前位置不偷的最大价值为上一位置偷或者不偷的最大价值
        }
        return Math.max(f[right], g[right]);
    }
}
